package com.algorithm.cn.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 
 * @author wangzonghui
 * @date 2021-01-05 20:11:20
 * @Description: 逆波兰表达式实现 支持多位数加减乘除
 */
public class PolandNotation {

	public static void main(String[] args) {
		/**
		 * 中缀表达式转后缀表达式
		 * 1、 1+((2+3)x4)-5 => 1 2 3 + 4 * + 5 -
		 * 2、因为直接对字符串操作不方便，因此先将 1+((2+3)x4)-5 转为 中缀表达式对应的list => [1,(,(,2,+3,),x,4,),-,5]
		 * 3、 遍历list转为后缀表达式
		 */
		String expression="1+((2+3)*4)-5";
		
		//中缀转list
		List<String> resultList=toInfixExpressIonList(expression);
		System.out.println(resultList);
		
		//list转后缀
		List<String> endList=parseSuffixExpressionList(resultList);
		System.out.println("后缀表达式："+endList+" 结果:"+calculate(endList));
		
		if(endList.size()>0) {
			return;
		}
		/**
		 * 中缀转后缀
		 * 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / +=76
		 * 3+4*5 -6 =>  3 4 + 5 * 6 - =29
		 */
		// 定义逆波兰表达式，为了表达方便，数字和符号间用空格隔开
		String  suffixExpression="4 5 * 8 - 60 + 8 2 / +";  //3+4*5-6
		//1、先将suffixExpression 放入arrayList中
		List<String> rpnList=getListString(suffixExpression);
		System.out.println(rpnList);
		
		//2、将ArrayList传递给一个方法，配合栈完成计算
		int res=calculate(rpnList);
		System.out.println("计算结果："+res);
	}
	
	public static List<String> parseSuffixExpressionList(List<String> ls){
		Stack<String> s1=new Stack<String>();  //符号栈
		List<String> s2 = new ArrayList<String>();
		
		for(String item:ls) {
			//如果为数，入栈
			if(item.matches("\\d+")) {
				s2.add(item);
			}else if(item.equals("(")) {
				s1.push(item);
			}else if(item.equals(")")) {
				//如果是右括号，以此弹出s1栈顶的运算符，并压入s2，知道遇到左括号卫视，此时将这对括号丢弃
				while(!s1.peek().equals("(")) {
					s2.add(s1.pop());
				}
				s1.pop();  //将括号弹出，消除小括号
				
			}else {
				//当s1的优先级小于等于栈顶的运算符优先级，将s1栈顶运算符弹出并压入s2中。
				while(s1.size()!=0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
					s2.add(s1.pop());
				}
				
				s1.push(item);
			}
		}
		
		//将s1剩余运算符压入s2中
		while(s1.size()!=0) {
			s2.add(s1.pop());
		}
		return s2;
	}
	/**
	 * 中缀表达式转对应list
	 * @param expression
	 * @return
	 */
	public static List<String> toInfixExpressIonList(String expression){
		List<String> arrayList = new ArrayList<String>();
		int i=0;  //临时指针用于遍历字符串
		String str;  //对多位数的拼接
		char c; //每遍历到一个字符，存储到c
		do {
			//如果c为非数字，加入到arrayList
			if((c=expression.charAt(i))<48|| (c=expression.charAt(i))>57) {  //非数字
				arrayList.add(c+"");
				i++;
				
			}else {  //数字
				str="";
				while(i<expression.length()&&(c=expression.charAt(i))>=48&&(c=expression.charAt(i))<=57) {
					str+=c;
					i++;
				}
				arrayList.add(str);
			}
			
		}while(i<expression.length());
		
		return arrayList;
	}
	/**
	 * 字符串按空格拆分
	 * @param suffixExpression
	 * @return
	 */
	public  static List<String> getListString(String suffixExpression){
		//将suffixExpression分割
		String[] split=suffixExpression.split(" ");
		List<String> list=new ArrayList<String>();
		for(String ele:split) {
			list.add(ele);
		}
		return list;
	}

	/**
	 * 逆波兰表达式计算
	 * 1) 从左到右，将数字压入栈
	 * @param ls
	 * @return
	 */
	public static int calculate(List<String> ls) {
		Stack<String> stack = new Stack<String>();
		for(String item:ls) {
			if(item.matches("\\d+")) {  //匹配多位数
				stack.push(item);
			}else {  //pop两个数，先计算再入栈
				int num2=Integer.parseInt(stack.pop());
				int num1=Integer.parseInt(stack.pop());
				int res=0;
				if(item.equals("+")) {
					res=num1 + num2;
				}else if(item.equals("-")) {
					res=num1 - num2;
				}else if(item.equals("*")) {
					res=num1 * num2;
				}else if(item.equals("/")) {
					res=num1 / num2;
				}else {
					System.out.println(item);
					throw new RuntimeException("云算符有误");
				}
				//入栈
				stack.push(res+"");
			}
		}
		return Integer.parseInt(stack.pop());
	}
}


//编写operation，返回对应运算符优先级
class Operation{
	private static int ADD=1;
	private static int SUB=1;
	private static int MUL=2;
	private static int DIV=2;
	
	public static int getValue(String operation) {
		int result=0;
		switch(operation) {
		case "+":
			result=ADD;
			break;
		case "-":
			result=SUB;
			break;
		case "*":
			result=MUL;
			break;
		case "/":
			result=DIV;
			break;
		default:
			System.out.println("No Found This Operation"+operation);
			break;
		}
		return result;
	}
}